UVa/11590 - Prefix lookup/11590.4.cpp

   1 //WA!
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define D(x) cout << #x " is " << (x) << endl
  24
  25 typedef unsigned long long Int;
  26 const int BUFSIZE = 256;
  27 char buf[BUFSIZE];
  28
  29 typedef bitset<100> num;
  30
  31 num operator +(num a, num b){
  32 }
  33
  34 int M;
  35 map<string, Int> ans;
  36
  37 struct node{
  38   node * left, * right;
  39   bool end; //is this node a complete prefix?
  40   node(bool e) : end(e) {
  41     left = right = NULL;
  42   }
  43 };
  44
  45 //not used, because I love to waste memory (It makes me feel dangerous)
  46 void clean(node * n){
  47   if (n == NULL) return;
  48   clean(n->left); clean(n->right);
  49   delete n;
  50 }
  51
  52 Int f(string s, node * n){ //s = string built so far, n = the node we are standing at
  53   Int left = 0, right = 0;
  54   if (n->left != NULL){
  55     left = f(s + "0", n->left);
  56   }
  57   if (n->right != NULL){
  58     right = f(s + "1", n->right);
  59   }
  60   if (n->end){
  61     Int x = ((1ULL) << (M - s.size())) - 1;
  62     if (M - s.size() == 64){
  63       x = ~(0ULL);
  64     }
  65     ans[s] = x - left + 1 - right;
  66   }
  67   Int ret = 0;
  68   if (n->end){
  69     ret = ans[s];
  70   }
  71   return ret + left + right;
  72 }
  73
  74 int main(){
  75   int n;
  76   while (scanf("%d %d\n", &n, &M)==2 && !(n == 0 && M == 0)){
  77     ans.clear();
  78     node * root = new node(true);
  79     while (n--){
  80       fgets(buf, BUFSIZE, stdin);
  81       node * cur = root;
  82       for (int i=0; ; ++i){
  83         if (buf[i] == '*'){
  84           cur->end = true;
  85           break;
  86         }
  87         if (buf[i] == '0'){
  88           if (cur->left == NULL) cur->left = new node(false);
  89           cur = cur->left;
  90         }else if (buf[i] == '1'){
  91           if (cur->right == NULL) cur->right = new node(false);
  92           cur = cur->right;
  93         }
  94       }
  95     }
  96
  97     f("", root);
  98
  99     int K;
 100     scanf("%d\n", &K);
 101     while (K--){
 102       fgets(buf, BUFSIZE, stdin);
 103       buf[strlen(buf)-2] = '\0'; //delete *\n
 104       Int t = ans[string(buf)];
 105       assert(t >= 0);
 106       printf("%llu\n", t);
 107     }
 108
 109     fgets(buf, BUFSIZE, stdin); //empty line
 110     puts("");
 111   }
 112   return 0;
 113 }